package tree.迭代bfs;

import po.TreeNode;

import java.util.Stack;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 前序遍历构造二叉搜索树1008.java
 * @Description TODO https://leetcode-cn.com/problems/construct-binary-search-tree-from-preorder-traversal/
 * @createTime 2021年03月28日 12:18:00
 */
public class 前序遍历构造二叉搜索树1008 {

    public TreeNode bstFromPreorder(int[] preorder) {
        Stack<TreeNode> stack = new Stack<>();
        int rootVal = preorder[0];
        TreeNode root = new TreeNode(rootVal);
        stack.push(root);
        for (int i = 1; i < preorder.length; i++) {
            TreeNode node = new TreeNode(preorder[i]);
            //todo 如果比栈顶元素小，表示的就是左子树节点
            if (stack.peek().val > preorder[i]) {
                stack.peek().left = node;
            } else {
                //todo 进入这里表示进入了右子树，需要先找到对应的根节点, 也就是比当前节点大的节点，直到栈为空
                TreeNode peek = stack.peek();
                while (!stack.isEmpty() && peek.val < preorder[i]) {
                    peek = stack.pop();
                }
                peek.right=node;
            }
            stack.push(node);
        }
        return root;
    }
}
